package Day2025_03_08;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode1926 {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis = new boolean[101][101];
    public int nearestExit(char[][] maze, int[] e) {
        int m = maze.length, n = maze[0].length;
        int step = 0;
        int a = e[0], b = e[1];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{a, b});
        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            for (int k = 0; k < sz; k++) {
                int[] tmp = q.poll();
                a = tmp[0];
                b = tmp[1];
                vis[a][b] = true;
                for(int i = 0; i < 4; i++) {
                    int cur1 = a + dx[i], cur2 = b + dy[i];
                    if (cur1 >= 0 && cur1 < m && cur2 >= 0 && cur2 <n && maze[cur1][cur2] == '.' && !vis[cur1][cur2]) {
                        q.add(new int[]{cur1, cur2});
                        vis[cur1][cur2] = true;
                        if (cur1 == 0 || cur1 == m - 1 || cur2 == 0 || cur2 == n - 1) return step;
                    }
                }
            }
        }
        return -1;
    }
}
